home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
FishMarket 1.0
/
FishMarket v1.0.iso
/
fishies
/
551-575
/
disk_559
/
rexxrmf
/
rexxrmflib.lzh
/
avl.structs.h
< prev
next >
Wrap
C/C++ Source or Header
|
1991-09-11
|
8KB
|
225 lines
/*:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::*
*:: ::*
*:: An implementaion of an AVL-Tree (balanced binary tree). ::*
*:: ::*
*:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::*/
#define MAXKEYLEN ((ULONG) 100) /* maximum length of a key */
#define MAXINDICES ((ULONG) 8) /* maximum number of indices */
/* 0-5, 0=primary, 1-5=alt */
/* 6=notused */
/* 7=deleted file blocks */
#define DELETEINDEX ((ULONG) 7)
#define MAXINDEXNUM ((ULONG) 5) /* max user index */
/*** Key Data Structure ***/
struct Keydata
{
USHORT occurence; /* when duplicate keys allowed, specifies the */
/* occurence number of the node. Otherwise = 1 */
USHORT keylen; /* length of the key data */
char *kdata; /* pointer to key data */
};
/*** Tree Node Structure ***/
/* The binary tree is built */
/* using this structure */
struct AvlNode
{
struct AvlNode *llink; /* points to the left child of this node */
struct AvlNode *rlink; /* points to the right child of this node */
struct AvlNode *parent; /* points to the parent of this node */
/* follow up the tree, gives you the path */
struct AvlNode *primary; /* alternates point to their primary node */
struct AvlNode *alternatekeys[MAXINDICES]; /* primary points to alts */
/* following fields used internally by AVL algorithm */
struct AvlNodeInfo {
SHORT balance;
USHORT inxnum;
ULONG rank;
} avi;
/* this part of the node stores data associated with the key */
struct AvlUserData
{
ULONG recaddr; /* This is assumed to be record */
/* location in some external file */
/* for this key. This value gets */
/* saved in the index file. */
ULONG blklen; /* block length of data */
struct Keydata *key; /* pointer to the key value */
APTR userdata1; /* any data/pointer to data */
APTR userdata2; /* any data/pointer to data */
/* userdata1&2 are not saved in */
/* the index file. */
} aud;
} ; /* End Structure AvlNode */
/*** Structure of the Index File ***/
/* */
/* this is the index file header */
/* It is loaded when the index file */
/* is opened. The AVL functions */
/* return a pointer to this struct */
/* for use in accessing the index */
/* OPEN_RMF/MAKE_INDEX return a */
/* pointer to this structure */
/* */
/*************************************/
struct IndexFile
{
USHORT xid; /* identifies file as an index */
ULONG datestamp; /* not used */
ULONG numberofrecords; /* number of keys in the index */
ULONG compares; /* number of comparisons made during */
/* search. (has no meaning at open) */
ULONG height; /* the height of the binary tree */
/* (has no meaning at open time) */
USHORT doserror; /* set to 0 if no errors occured */
USHORT rmferror; /* set to 0 if no errors occured */
/* otherwise set to error code as */
/* defined above. */
ULONG prevpos; /* relative positions of previous key */
/* retrieved. (meaningless at open) */
ULONG rba_primary; /* location where index entries begin.*/
/* should be valued. Tells where the */
/* first index entry is located in */
/* the index file. */
ULONG fd_primary; /* file handle for the index file */
/* filled in at open time */
ULONG fd_data; /* file handle for the data file */
/* filled in at open time */
UBYTE *indxname; /* points to filename of index file */
UBYTE *filename; /* points to filename of data file */
UBYTE *cmp1;
UBYTE *cmp2;
LONG cmpl1;
LONG cmpl2;
struct AvlNode *MRNode; /* most recent AvlNode returned */
struct AvlNode *PrevSrchKey[MAXINDICES];
struct AvlNode *SearchNode[MAXINDICES];
struct AvlNode *IndexRoot[MAXINDICES];
/* previous search type 'K','P','R', 'U' */
UBYTE prev_srch_type[MAXINDICES];
UBYTE dups; /* set to 1 if duplicates allowed */
/* otherwise set to 0 */
};
/*** Structure of the Index File Entries ***/
/* repeats for each primary key in file */
struct DiskIndex
{
struct DI_Info {
ULONG recaddr; /* record location for this key */
/* this is the location of a data */
/* record in some external file. */
USHORT blklength; /* length of record */
UBYTE rectype; /* record type ??? dreaming I guess */
UBYTE recstatus; /* record status = 'A'/'D' */
/* 'A' active record */
/* a 'A' will have its keys (from */
/* below) loaded in the corresponding */
/* index. ie. if keylen[3] is non zero */
/* then keydata[3] is loaded in index */
/* three. */
/* 'D' deleted record */
/* a 'D' record block automatically */
/* gets loaded into the DELETEINDEX */
/* regardless of the keylen info. */
USHORT keylen[MAXINDICES]; /* length of the key */
} di_info;
UBYTE keydata[MAXKEYLEN*MAXINDICES]; /* the actual key value. */
/* keylen says how long, */
/* these are not NULL */
/* terminated. */
} ;
struct RecordHeader
{
SHORT blockid; /* not used */
LONG blocklength;
SHORT dataoffset;
SHORT spare0; /* not used */
SHORT recordlength;
SHORT numberoffields;
ULONG datestamp; /* not used */
LONG spare1;
SHORT spare2;
SHORT numaltindx;
};
struct DataFileHeader
{
SHORT fileid; /* not used */
ULONG datestamp; /* not used */
LONG spare0;
LONG spare1;
SHORT spare2;
SHORT spare3;
SHORT spare4;
};
struct EOR_Trailer
{
UBYTE eor[4];
};